#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // @ysh's method
    // int jump(vector<int> &nums)
    // {
    //     reverse(nums.begin(), nums.end());
    //     vector<int> dp(nums.size(), 0);
    //     for (int i = 1; i < (int)nums.size(); i++)
    //     {
    //         dp[i] = INT_MAX - 1;
    //         int start_index = i - nums[i];
    //         if (i - nums[i] < 0)
    //         {
    //             start_index = 0;
    //         }
    //         for (int j = start_index; j < i; j++)
    //         {
    //             dp[i] = min(dp[i], dp[j] + 1);
    //         }
    //     }
    //     return dp[nums.size() - 1];
    // }

    // @book's method
    // int jump(vector<int> &nums)
    // {
    //     if (nums.size() == 1)
    //     {
    //         return 0;
    //     }
    //     int cur_index = 0;
    //     int next_index = 0;
    //     int step = 0;
    //     for (int i = 0; i < (int)nums.size(); i++)
    //     {
    //         next_index = max(i + nums[i], next_index);
    //         if (i == cur_index)
    //         {
    //             step++;
    //             cur_index = next_index;
    //             if (next_index >= (int)nums.size() - 1)
    //             {
    //                 break;
    //             }
    //         }
    //     }
    //     return step;
    // }

    int jump(vector<int> &nums)
    {
        int cur_index = 0;
        int next_index = 0;
        int step = 0;
        for (int i = 0; i < (int)nums.size() - 1; i++)
        {
            next_index = max(i + nums[i], next_index);
            if (i == cur_index)
            {
                step++;
                cur_index = next_index;
            }
        }
        return step;
    }
};

int main()
{
    vector<int> nums{2, 3, 0, 1, 4};
    Solution sol;
    cout << sol.jump(nums) << endl;
    return 0;
}